<html lang="zh-CN"><head><meta charset="UTF-8"><style>.nodata  main {width:1000px;margin: auto;}</style></head><body class="nodata " style=""><div class="main_father clearfix d-flex justify-content-center " style="height:100%;"> <div class="container clearfix " id="mainBox"><main><div class="blog-content-box">
<div class="article-header-box">
<div class="article-header">
<div class="article-title-box">
<h1 class="title-article" id="articleContentId">(A卷,200分)- 计算网络信号、信号强度（Java & JS & Python & C）</h1>
</div>
</div>
</div>
<div id="blogHuaweiyunAdvert"></div>

        <div id="article_content" class="article_content clearfix">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/kdoc_html_views-1a98987dfd.css">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/ck_htmledit_views-044f2cf1dc.css">
                <div id="content_views" class="htmledit_views">
                    <h4 id="main-toc">题目描述</h4> 
<p>网络信号经过传递会逐层衰减&#xff0c;且遇到阻隔物无法直接穿透&#xff0c;在此情况下需要计算某个位置的网络信号值。<br /> 注意:网络信号可以绕过阻隔物。</p> 
<p>array[m][n] 的二维数组代表网格地图&#xff0c;<br /> array[i][j] &#61; <strong>0</strong>代表i行j列是空旷位置;<br /> array[i][j] &#61; <strong>x</strong>(x为正整数)代表i行j列是信号源&#xff0c;信号强度是x;<br /> array[i][j] &#61; <strong>-1</strong>代表i行j列是阻隔物。<br /> 信号源只有1个&#xff0c;阻隔物可能有0个或多个<br /> 网络信号衰减是上下左右相邻的网格衰减1<br /> 现要求输出<strong>对应位置的网络信号值</strong>。</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%85%A5%E6%8F%8F%E8%BF%B0">输入描述</h4> 
<p>输入为三行&#xff0c;第一行为 m 、n &#xff0c;代表输入是一个 m × n 的数组。<br /> 第二行是一串 m × n 个用空格分隔的整数.<br /> 每连续 n 个数代表一行&#xff0c;再往后 n 个代表下一行&#xff0c;以此类推。<br /> 对应的值代表对应的网格是空旷位置&#xff0c;还是信号源&#xff0c;还是阻隔物。<br /> 第三行是 i 、 j&#xff0c;代表需要计算array[i][j]的网络信号值。<br /> 注意&#xff1a;此处 i 和 j 均从 0 开始&#xff0c;即第一行 i 为 0。</p> 
<p>例如</p> 
<p><code>6 5</code><br /><code>0 0 0 -1 0 0 0 0 0 0 0 0 -1 4 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0</code><br /><code>1 4</code><br /> 代表如下地图</p> 
<p><img alt="" height="281" src="https://img-blog.csdnimg.cn/86ba6e48f2e34e978f338c99a1b3b367.png" width="283" /></p> 
<p>需要输出第1行第4列的网络信号值&#xff0c;如下图&#xff0c;值为2。</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%87%BA%E6%8F%8F%E8%BF%B0">输出描述</h4> 
<p>输出对应位置的网络信号值&#xff0c;如果网络信号未覆盖到&#xff0c;也输出0。<br /> 一个网格如果可以途径不同的传播衰减路径传达&#xff0c;取较大的值作为其信号值。</p> 
<p></p> 
<h4 id="%E7%94%A8%E4%BE%8B">用例</h4> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;">6 5<br /> 0 0 0 -1 0 0 0 0 0 0 0 0 -1 4 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0<br /> 1 4</td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;">2</td></tr><tr><td style="width:86px;">说明</td><td style="width:412px;">无</td></tr></tbody></table> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;">6 5<br /> 0 0 0 -1 0 0 0 0 0 0 0 0 -1 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0<br /> 2 1</td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;">0</td></tr><tr><td style="width:86px;">说明</td><td style="width:412px;">无</td></tr></tbody></table> 
<p></p> 
<h4 id="%E9%A2%98%E7%9B%AE%E8%A7%A3%E6%9E%90">题目解析</h4> 
<p>用例图示如下</p> 
<p><img alt="" height="298" src="https://img-blog.csdnimg.cn/4ce2f9931fd747ad9b374ce7566b8b86.png" width="649" /></p> 
<p> 因此[1,4]位置&#xff08;如上图红框位置&#xff09;的值为2。</p> 
<p></p> 
<p>通过图示&#xff0c;我们可以很容易想到解题思路是图的多源BFS。</p> 
<p>因此&#xff0c;题解请参考&#xff1a;</p> 
<p><a href="https://blog.csdn.net/qfc_128220/article/details/127711317?spm&#61;1001.2014.3001.5501" title="华为机试 - 计算疫情扩散时间_伏城之外的博客-CSDN博客">华为机试 - 计算疫情扩散时间_伏城之外的博客-CSDN博客</a></p> 
<p><a href="https://blog.csdn.net/qfc_128220/article/details/128169190?spm&#61;1001.2014.3001.5501" title="华为机试 - 污染水域_伏城之外的博客-CSDN博客">华为机试 - 污染水域_伏城之外的博客-CSDN博客</a></p> 
<p></p> 
<h4 id="%E7%AE%97%E6%B3%95%E6%BA%90%E7%A0%81">JavaScript算法源码</h4> 
<pre><code class="language-javascript">/* JavaScript Node ACM模式 控制台输入获取 */
const readline &#61; require(&#34;readline&#34;);

const rl &#61; readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines &#61; [];
rl.on(&#34;line&#34;, (line) &#61;&gt; {
  lines.push(line);

  if (lines.length &#61;&#61;&#61; 3) {
    const [m, n] &#61; lines[0].split(&#34; &#34;).map(Number);
    const arr &#61; lines[1].split(&#34; &#34;).map(Number);
    const pos &#61; lines[2].split(&#34; &#34;).map(Number);
    console.log(getResult(arr, m, n, pos));
    lines.length &#61; 0;
  }
});

function getResult(arr, m, n, pos) {
  let queue &#61; [];

  for (let i &#61; 0; i &lt; m; i&#43;&#43;) {
    for (let j &#61; 0; j &lt; n; j&#43;&#43;) {
      if (arr[i * n &#43; j] &gt; 0) {
        queue.push([i, j]);
        break;
      }
    }
  }

  // 上下左右偏移量
  const offset &#61; [
    [-1, 0],
    [1, 0],
    [0, -1],
    [0, 1],
  ];

  while (queue.length) {
    const newQueue &#61; []; // 此时不使用queue.shift操作&#xff0c;因为此步操每次都需要O(n)时间&#xff0c;无法应对大数量级情况

    for (const [i, j] of queue) {
      const x &#61; arr[i * n &#43; j] - 1;

      if (x &#61;&#61;&#61; 0) break;

      for (let [offsetX, offsetY] of offset) {
        const newI &#61; i &#43; offsetX;
        const newJ &#61; j &#43; offsetY;

        if (
          newI &gt;&#61; 0 &amp;&amp;
          newI &lt; m &amp;&amp;
          newJ &gt;&#61; 0 &amp;&amp;
          newJ &lt; n &amp;&amp;
          arr[newI * n &#43; newJ] &#61;&#61;&#61; 0
        ) {
          arr[newI * n &#43; newJ] &#61; x;
          newQueue.push([newI, newJ]);
        }
      }
    }

    queue &#61; newQueue;
  }

  const [tarI, tarJ] &#61; pos;
  return arr[tarI * n &#43; tarJ];
}
</code></pre> 
<p></p> 
<h4>Java算法源码</h4> 
<pre><code class="language-java">import java.util.LinkedList;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc &#61; new Scanner(System.in);

    int m &#61; sc.nextInt();
    int n &#61; sc.nextInt();

    int[] arr &#61; new int[m * n];
    for (int i &#61; 0; i &lt; m * n; i&#43;&#43;) {
      arr[i] &#61; sc.nextInt();
    }

    int tarI &#61; sc.nextInt();
    int tarJ &#61; sc.nextInt();

    System.out.println(getResult(arr, m, n, tarI, tarJ));
  }

  public static int getResult(int[] arr, int m, int n, int tarI, int tarJ) {
    LinkedList&lt;Integer[]&gt; queue &#61; new LinkedList&lt;&gt;();

    for (int i &#61; 0; i &lt; m; i&#43;&#43;) {
      for (int j &#61; 0; j &lt; n; j&#43;&#43;) {
        if (arr[i * n &#43; j] &gt; 0) {
          queue.addLast(new Integer[] {i, j});
          break;
        }
      }
    }

    // 上下左右偏移量
    int[][] offsets &#61; {<!-- -->{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    while (queue.size() &gt; 0) {
      Integer[] pos &#61; queue.removeFirst();
      int i &#61; pos[0];
      int j &#61; pos[1];

      int x &#61; arr[i * n &#43; j] - 1;

      if (x &#61;&#61; 0) break;

      for (int[] offset : offsets) {
        int newI &#61; i &#43; offset[0];
        int newJ &#61; j &#43; offset[1];

        if (newI &gt;&#61; 0 &amp;&amp; newI &lt; m &amp;&amp; newJ &gt;&#61; 0 &amp;&amp; newJ &lt; n &amp;&amp; arr[newI * n &#43; newJ] &#61;&#61; 0) {
          arr[newI * n &#43; newJ] &#61; x;
          queue.addLast(new Integer[] {newI, newJ});
        }
      }
    }

    return arr[tarI * n &#43; tarJ];
  }
}
</code></pre> 
<p></p> 
<h4 style="background-color:transparent;">Python算法源码</h4> 
<pre><code class="language-python"># 输入获取
m, n &#61; map(int, input().split())
arr &#61; list(map(int, input().split()))
pos &#61; list(map(int, input().split()))


# 算法入口
def getResult(arr, m, n, pos):
    queue &#61; []

    for i in range(m):
        for j in range(n):
            if arr[i * n &#43; j] &gt; 0:
                queue.append([i, j])
                break

    offsets &#61; ((-1, 0), (1, 0), (0, -1), (0, 1))

    while len(queue) &gt; 0:

        newQueue &#61; []

        for i, j in queue:
            x &#61; arr[i * n &#43; j] - 1

            if x &#61;&#61; 0:
                break

            for offsetX, offsetY in offsets:
                newI &#61; i &#43; offsetX
                newJ &#61; j &#43; offsetY

                if 0 &lt;&#61; newI &lt; m and 0 &lt;&#61; newJ &lt; n and arr[newI * n &#43; newJ] &#61;&#61; 0:
                    arr[newI * n &#43; newJ] &#61; x
                    newQueue.append([newI, newJ])

        queue &#61; newQueue

    tarI, tarJ &#61; pos
    return arr[tarI * n &#43; tarJ]


# 算法调用
print(getResult(arr, m, n, pos))
</code></pre> 
<p></p> 
<h4>C算法源码</h4> 
<pre><code class="language-cpp">#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;

typedef struct ListNode {
    int ele;
    struct ListNode *next;
} ListNode;

typedef struct {
    int size;
    ListNode *head;
    ListNode *tail;
} LinkedList;

LinkedList *new_LinkedList();
void addLast_LinkedList(LinkedList *link, int ele);
int removeFirst_LinkedList(LinkedList* link);

int getResult(int nums[], int m, int n, int tarI, int tarJ);

int main() {
    int m, n;
    scanf(&#34;%d %d&#34;, &amp;m, &amp;n);

    int nums[m*n];
    for(int i&#61;0; i&lt;m*n; i&#43;&#43;) {
        scanf(&#34;%d&#34;, &amp;nums[i]);
    }

    int tarI, tarJ;
    scanf(&#34;%d %d&#34;, &amp;tarI, &amp;tarJ);

    printf(&#34;%d\n&#34;, getResult(nums, m, n, tarI, tarJ));

    return 0;
}

int getResult(int nums[], int m, int n, int tarI, int tarJ) {
    LinkedList* queue &#61; new_LinkedList();

    for(int i&#61;0; i&lt;m; i&#43;&#43;) {
        for(int j&#61;0; j&lt;n; j&#43;&#43;) {
            if(nums[i * n &#43; j] &gt; 0) {
                addLast_LinkedList(queue, i * n &#43; j);
                break;
            }
        }
    }

    int offsets[4][2] &#61; {<!-- -->{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    while(queue-&gt;size &gt; 0) {
        int pos &#61; removeFirst_LinkedList(queue);

        int i &#61; pos / n;
        int j &#61; pos % n;

        int x &#61; nums[i * n &#43; j] - 1;

        if(x &#61;&#61; 0) break;

        for(int k&#61;0; k&lt;4; k&#43;&#43;) {
            int newI &#61; i &#43; offsets[k][0];
            int newJ &#61; j &#43; offsets[k][1];

            if(newI &gt;&#61; 0 &amp;&amp; newI &lt; m &amp;&amp; newJ &gt;&#61; 0 &amp;&amp; newJ &lt; n &amp;&amp; nums[newI * n &#43; newJ] &#61;&#61; 0) {
                nums[newI * n &#43; newJ] &#61; x;
                addLast_LinkedList(queue, newI * n &#43; newJ);
            }
        }
    }

    return nums[tarI * n &#43; tarJ];
}

LinkedList *new_LinkedList() {
    LinkedList *link &#61; (LinkedList *) malloc(sizeof(LinkedList));

    link-&gt;size &#61; 0;
    link-&gt;head &#61; NULL;
    link-&gt;tail &#61; NULL;

    return link;
}

void addLast_LinkedList(LinkedList *link, int ele) {
    ListNode *node &#61; (ListNode *) malloc(sizeof(ListNode));

    node-&gt;ele &#61; ele;
    node-&gt;next &#61; NULL;

    if (link-&gt;size &#61;&#61; 0) {
        link-&gt;head &#61; node;
        link-&gt;tail &#61; node;
    } else {
        link-&gt;tail-&gt;next &#61; node;
        link-&gt;tail &#61; node;
    }

    link-&gt;size&#43;&#43;;
}

int removeFirst_LinkedList(LinkedList* link) {
    if(link-&gt;size &#61;&#61; 0) exit(-1);

    ListNode* removed &#61; link-&gt;head;

    if(link-&gt;size &#61;&#61; 1) {
        link-&gt;head &#61; NULL;
        link-&gt;tail &#61; NULL;
    } else {
        link-&gt;head &#61; link-&gt;head-&gt;next;
    }

    link-&gt;size--;

    int res &#61; removed-&gt;ele;

    free(removed);

    return res;
}</code></pre> 
<p> </p>
                </div>
        </div>
        <div id="treeSkill"></div>
        <div id="blogExtensionBox" style="width:400px;margin:auto;margin-top:12px" class="blog-extension-box"></div>
    <script>
  $(function() {
    setTimeout(function () {
      var mathcodeList = document.querySelectorAll('.htmledit_views img.mathcode');
      if (mathcodeList.length > 0) {
        for (let i = 0; i < mathcodeList.length; i++) {
          if (mathcodeList[i].naturalWidth === 0 || mathcodeList[i].naturalHeight === 0) {
            var alt = mathcodeList[i].alt;
            alt = '\\(' + alt + '\\)';
            var curSpan = $('<span class="img-codecogs"></span>');
            curSpan.text(alt);
            $(mathcodeList[i]).before(curSpan);
            $(mathcodeList[i]).remove();
          }
        }
        MathJax.Hub.Queue(["Typeset",MathJax.Hub]);
      }
    }, 1000)
  });
</script>
</div></html>